package leetcode;

/**
 * @author caifangyi
 * @date 2022/7/21
 */

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * 移动零
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 请注意，必须在不复制数组的情况下原地对数组进行操作。
 *
 * 
 *
 * 示例 1:
 *
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 示例 2:
 *
 * 输入: nums = [0]
 * 输出: [0]
 * 
 *
 * 提示:
 *
 * 1 <= nums.length <= 104
 * -231<= nums[i] <= 231- 1
 * 
 *
 * 进阶：你能尽量减少完成的操作次数吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/move-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Day0283 {

    public static void main(String[] args) {
        int[] nums = {0,1,0,3,12};
        Solution2 solution = new Solution2();
        solution.moveZeroes(nums);
        String collect = Arrays.stream(nums).mapToObj(value -> String.valueOf(value)).collect(Collectors.joining(","));
        System.out.println(collect);
    }


    static class Solution2 {
        public void moveZeroes(int[] nums) {
            //双指针，遍历向右，发现0值时设置左右指针，之后右指针向右，左指针指向0
            //发现非0值，左右指针值交换，同时左指针右移一位

            int left = 0;
            int right =0;
            while(right < nums.length){

                //没有发现0的话，一直向右
                if(nums[right] != 0){
                    if(right != left){
                        nums[left] = nums[left] ^ nums[right];
                        nums[right] = nums[left] ^ nums[right];
                        nums[left] = nums[left] ^ nums[right];
                    }
                    left++;
                }
                right++;
            }

        }
    }

    static class Solution {
        public void moveZeroes(int[] nums) {
            //双指针，遍历向右，发现0值时设置左右指针，之后右指针向右，左指针指向0
            //发现非0值，左右指针值交换，同时左指针右移一位

            int left = 0;
            int right =0;
            boolean swap = false;
            while(right < nums.length){

                //左指针：没有发现0的话，一直向右，发现0的话，停止
                if(nums[left] != 0){
                     left++;
                }
                //右指针：没有发现0的话，一直向右，但是发现0后，标识开启，之后发现非0后，触发交换操作
                if(nums[right] != 0){
                    if(swap){
                        nums[left] = nums[left] ^ nums[right];
                        nums[right] = nums[left] ^ nums[right];
                        nums[left] = nums[left] ^ nums[right];
                        left++;
                    }
                }else{
                    swap = true;
                }
                right++;
            }

        }
    }
}
